1009. 十进制整数的反码【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 暴力解法
• 3. 🎯 s.2 - 数学
• 4. 🎯 s.3 - 掩码异或
• 5. 🔗 引用

1. 📝 题目描述

• leetcode

每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 "101"，11 可以用二进制 "1011" 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。

二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 "101" 的二进制反码为 "010"。

给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。

---

示例 1：

输入：5
输出：2
解释：5 的二进制表示为 "101"，其二进制反码为 "010"，也就是十进制中的 2。

示例 2：

输入：7
输出：0
解释：7 的二进制表示为 "111"，其二进制反码为 "000"，也就是十进制中的 0。

示例 3：

输入：10
输出：5
解释：10 的二进制表示为 "1010"，其二进制反码为 "0101"，也就是十进制中的 5。

---

提示：

1. 0 <= N < 10^9

注意

• 本题与 476. 数字的补数 相同
• 题解说明记录在 本题

2. 🎯 s.1 - 暴力解法

js

/**
 * @param {number} n
 * @return {number}
 */
var bitwiseComplement = function (n) {
  // 将数字转换为二进制字符串
  const binaryStr = n.toString(2)

  // 翻转每一位
  let complementStr = ''
  for (const bit of binaryStr) {
    complementStr += bit === '0' ? '1' : '0'
  }

  // 转换回十进制
  return parseInt(complementStr, 2)
}

• 时间复杂度：$O(logn)$，需要计算 n 的二进制位数
• 空间复杂度：$O(1)$，只使用了常数级别的额外空间

3. 🎯 s.2 - 数学

js

/**
 * @param {number} n
 * @return {number}
 */
var bitwiseComplement = function (n) {
  // 特殊情况处理
  if (n === 0) return 1

  // 找到大于 n 的最小 2 的幂次
  let powerOfTwo = 1
  while (powerOfTwo <= n) {
    powerOfTwo <<= 1 // 相当于 powerOfTwo *= 2
  }

  // 全1数 = powerOfTwo - 1
  // 反码 = 全1数 - 原数
  return powerOfTwo - 1 - n
}

• 时间复杂度：$O(logn)$，需要找到大于 n 的最小 2 的幂次
• 空间复杂度：$O(1)$，只使用了常数级别的额外空间
• $\mathrm{反}\mathrm{码}=\mathrm{全}1\mathrm{数}-\mathrm{原}\mathrm{数}$
  • $5(101)+2(010)=7(111)$
  • $10(1010)+5(0101)=15(1111)$

4. 🎯 s.3 - 掩码异或

js

/**
 * @param {number} n
 * @return {number}
 */
var bitwiseComplement = function (n) {
  // 找到 n 的二进制位数
  let bitLength = n.toString(2).length

  // 构造相同位数的全1掩码
  let mask = (1 << bitLength) - 1

  // 异或运算得到补数
  return n ^ mask
}

• 时间复杂度：$O(\log n)$，主要消耗在计算 n 的二进制位数上
• 空间复杂度：$O(\log n)$，主要消耗在 n.toString(2) 生成的二进制字符串上
• 算法思路：
  1. 计算输入数字的二进制位数
  2. 创建一个相同位数的全 1 掩码
  3. 使用异或运算（XOR）得到反码结果
• 执行示例 1、2、3：

示例 1：输入 5

let n = 5

// 步骤 1: 找到 n 的二进制位数
let bitLength = n.toString(2).length // "101".length = 3

// 步骤 2: 构造相同位数的全1掩码
let mask = (1 << bitLength) - 1 // (1 << 3) - 1 = 8 - 1 = 7 (二进制: 111)

// 步骤 3: 异或运算得到补数
return n ^ mask // 5 ^ 7 = 101 ^ 111 = 010 = 2

// 结果：2

示例 2：输入 7

let n = 7

// 步骤 1: 找到 n 的二进制位数
let bitLength = n.toString(2).length // "111".length = 3

// 步骤 2: 构造相同位数的全1掩码
let mask = (1 << bitLength) - 1 // (1 << 3) - 1 = 8 - 1 = 7 (二进制: 111)

// 步骤 3: 异或运算得到补数
return n ^ mask // 7 ^ 7 = 111 ^ 111 = 000 = 0

// 结果：0

示例 3：输入 10

let n = 10

// 步骤 1: 找到 n 的二进制位数
let bitLength = n.toString(2).length // "1010".length = 4

// 步骤 2: 构造相同位数的全1掩码
let mask = (1 << bitLength) - 1 // (1 << 4) - 1 = 16 - 1 = 15 (二进制: 1111)

// 步骤 3: 异或运算得到补数
return n ^ mask // 10 ^ 15 = 1010 ^ 1111 = 0101 = 5

// 结果：5

5. 🔗 引用

• 476. 数字的补数